/**
 * 插入排序算法,时间复杂度O(n^2) 
 * @author firebroo
 *
 */
public class InsertSortTest {

	public void insertionsort(int[] data){
		int tmp;                                                     //临时变量，保存需要排序的值
		int i, j;
		for(i=1;i<data.length;i++){
			tmp=data[i];
			for(j = i; j > 0 && tmp < data[j-1]; j--){          //将需要排序的值和前一个值进行对比
				data[j]=data[j-1];                          //将值后移一格
			}
			data[j]=tmp;                                       //将带排序的值插入正确位置
		}
	}

	/**
	 * 测试算法
	 * @param args
	 */
	public static void main(String[] args){
		InsertSortTest test=new InsertSortTest();
		int[] data={1,4,5,56,3,45,78};
		test.insertionsort(data);
		for(int i = 0;i < data.length;i++){
			System.out.println(data[i]);
		}
	}
}
